/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
#include"PublicAVLTree.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef enum {
AVLBF_LH=-1,	//左边高
AVLBF_EH=0,		//左右相等
AVLBF_RH=1		//右边高
}AVLBFTYPE;
typedef struct _AVLTREE{
uint64_t	key;//索引
void*		data;//数据
AVLBFTYPE	bf;//平衡值 
struct _AVLTREE*left;//左孩子
struct _AVLTREE*right;//右孩子
}AVLTREE;
//	  X		     Y
//	Y	3 =>   1   X
//1  2			  2  3
//左旋转
AVLTREE*L_Rotate(AVLTREE*root){
	AVLTREE*tmp=root;
	root=root->right;
	tmp->right=root->left;
	root->left=tmp;
	return root;
}
//右旋转
AVLTREE*R_Rotate(AVLTREE*root){
	AVLTREE*tmp=root;
	root=root->left;
	tmp->left=root->right;
	root->right=tmp;
	return root;
}
AVLTREE*LeftBalance(AVLTREE*root){
	return root;
}
AVLTREE*RightBalance(AVLTREE*root){
	AVLTREE*right=root->right;
	if(right->bf==AVLBF_RH){
		right->bf=AVLBF_EH;
		root->bf=AVLBF_EH;
		root=L_Rotate(root);
	}else
	if(right->bf==AVLBF_EH){
		right->bf=AVLBF_LH;
		root->bf=AVLBF_RH;
		root=L_Rotate(root);
	}else
//先右旋 后左选		
	if(right->bf==AVLBF_LH){
		root->right=R_Rotate(root->right);
		root=L_Rotate(root);
	}
	return root;
}
//插入数据,taller是否涨高
AVLTREE*_AVLTreeInsert(AVLTREE*root,AVLTREE*pos,int*taller){
	if(root==NULL){
		*taller=1;
		return pos;
	}
	if(root->key>pos->key){
		root->left=_AVLTreeInsert(root->left,pos,taller);
		if(*taller==1){
			if(root->bf==AVLBF_EH){
				root->bf=AVLBF_LH;
				*taller=1;
			}else
//连续2次左高				
			if(root->bf==AVLBF_LH){
				*taller=0;
				root=LeftBalance(root);
			}else
//左右平衡				
			if(root->bf==AVLBF_RH){
				*taller=0;
				root->bf=AVLBF_EH;
			}
		}
	}else{
		root->right=_AVLTreeInsert(root->right,pos,taller);
		if(*taller==1){		
			if(root->bf==AVLBF_EH){
				root->bf=AVLBF_RH;
				*taller=1;
			}else
//连续2次左高				
			if(root->bf==AVLBF_RH){
				*taller=0;
				root=RightBalance(root);
			}else
//左右平衡				
			if(root->bf==AVLBF_LH){
				*taller=0;
				root->bf=AVLBF_EH;
			}
		}
	}   	
	return root;
}
AVLTREEHANDLE AVLTreeInsert(AVLTREEHANDLE hHandle,uint64_t key,void*data){
	AVLTREE*root=(AVLTREE*)hHandle;
	AVLTREE*pos=(AVLTREE*)malloc(sizeof(AVLTREE));
	memset(pos,0,sizeof(AVLTREE));
	pos->key=key;
	pos->data=data;
//根为空
	if(root==NULL){
		root=pos;
	}else{
		int taller=0;
		root=_AVLTreeInsert(root,pos,&taller);
	}	
	return root;
}
//删除数据
AVLTREEHANDLE AVLTreeDelete(AVLTREEHANDLE hHandle,uint64_t key,AVLTreeFun pFun){
	return NULL;
}
//更新数据
AVLTREEHANDLE AVLTreeUpdate(AVLTREEHANDLE hHandle,uint64_t key,AVLTreeFun pFun){
	return NULL;
}
//遍历数据
void _AVLTreeLookUp(AVLTREEHANDLE hHandle,AVLTreeFun pFun,int deep){
	AVLTREE*root=(AVLTREE*)hHandle;
	if(root==NULL){
		return;
	}
	if(root->left!=NULL){
		_AVLTreeLookUp(root->left,pFun,deep+1);
	}
	printf("key:%ld deep:%d\n",root->key,deep);
	if(pFun!=NULL){
		pFun(root->key,root->data);
	}
	if(root->right!=NULL){
		_AVLTreeLookUp(root->right,pFun,deep+1);
	}
}
void AVLTreeLookUp(AVLTREEHANDLE hHandle,AVLTreeFun pFun){
	AVLTREE*root=(AVLTREE*)hHandle;
	if(root==NULL){
		return;
	}
	if(root->left!=NULL){
		_AVLTreeLookUp(root->left,pFun,0);
	}
	printf("key:%ld deep:root\n",root->key);
	if(pFun!=NULL){
		pFun(root->key,root->data);
	}
	if(root->right!=NULL){
		_AVLTreeLookUp(root->right,pFun,0);
	}
}
//清空数据
AVLTREEHANDLE AVLTreeClean(AVLTREEHANDLE hHandle,AVLTreeFun pFun){
	AVLTREE*root=(AVLTREE*)hHandle;
	if(root==NULL){
		return;
	}
	if(root->left!=NULL){
		AVLTreeClean(root->left,pFun);
	}
	if(pFun!=NULL){
		pFun(root->key,root->data);
	}
	if(root->right!=NULL){
		AVLTreeClean(root->right,pFun);
	}
	free(root);
	return NULL;
}